package com.nlp.algorithm.greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * 贪心算法
 * 有n个需要在同一天使用同一个教室的活动a1,a2,…,an，
 * 教室同一时刻只能由一个活动使用。每个活动ai都有一
 * 个开始时间si和结束时间fi 。一旦被选择后，活动ai就占
 * 据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj
 * 两个活动就可以被安排在这一天。该问题就是要安排这些
 * 活动使得尽量多的活动能不冲突的举行。例如下图所示的
 * 活动集合S，其中各项活动按照结束时间单调递增排序。
 * i		1	|	2	|	3		|	4	 |	5	|	6	|	7	|	8	|	9	|	10		|	11
 * s[i]		1	|	3	|	0		|	5	 |	3	|	5	|	6	|	8	|	8	|	2		|	12
 * f[i]		4	|	5	|	6		|	7	 |	8	|	9	|	10	|	11	|	12	|	13		|	14
 * 用贪心法的话思想很简单：活动越早结束，剩余的时间是不
 * 是越多？那我就早最早结束的那个活动，找到后在剩下的活
 * 动中再找最早结束的不就得了？
 * 
 * 虽然贪心算法的思想简单，但是贪心法不保证能得到问题的
 * 最优解，如果得不到最优解，那就不是我们想要的东西了，
 * 所以我们现在要证明的是在这个问题中，用贪心法能得到最优解。
 * @author ygsong.abcft
 *
 */
public class ActiveTime {
	
	
	public static void main(String[] args) {
		// 创建活动并添加到集合中
		Active act1 = new Active(1, 4);
		Active act2 = new Active(3, 5);
		Active act3 = new Active(0, 6);
		Active act4 = new Active(5, 7);
		Active act5 = new Active(3, 8);
		Active act6 = new Active(5, 9);
		Active act7 = new Active(6, 10);
		Active act8 = new Active(8, 11);
		Active act9 = new Active(8, 12);
		Active act10 = new Active(2, 13);
		Active act11 = new Active(12, 14);

		List<Active> actives = new ArrayList<Active>();
		actives.add(act1);
		actives.add(act2);
		actives.add(act3);
		actives.add(act4);
		actives.add(act5);
		actives.add(act6);
		actives.add(act7);
		actives.add(act8);
		actives.add(act9);
		actives.add(act10);
		actives.add(act11);
		ActiveTime activeTime = new ActiveTime();
		List<Active> bestActivites = activeTime.getBestActivites(actives, 0, 16);
		for (int i = 0; i < bestActivites.size(); i++) {
			System.out.println(bestActivites.get(i));
		}
	}
	

	/**
	 * 
	 * @param actives 活动集合
	 * @param startTime 教室的开始使用时间
	 * @param endTime 教室的结束使用时间
	 * @return
	 */
	public List<Active> getBestActivites(List<Active> actives, int startTime, int endTime){
		//最佳活动选择集合
		List<Active> bestActives = new ArrayList<Active>();
		//将活动按照最早结束时间排序
		actives.sort(null);
		//nowTime用来记录上次活动结束时间
		int nowTime = startTime;
		/***
		 * 因为我们已经按照最早结束时间排序，那么只要活动在时间范围内
		 * actives.get(1)就应当是第一个活动的结束时间
		 * 则我们记录第一次活动结束的时间，在结合剩下的活动中
		 * 选取开始时间大于nowTime且结束时间又在范围内的活动，则为第二次活动时间
		 * 直到选出所有活动
		 */
		for (int i = 0; i < actives.size(); i++) {
			Active act = actives.get(i);
			if (act.getStartTime() > nowTime && act.getEndTime() < endTime) {
				bestActives.add(act);
				nowTime = act.getEndTime();
			}
		}
		return bestActives;
	}
	
	

}

class Active implements Comparable<Active>{
	/**开始时间*/
	private int startTime;
	/**结束时间*/
	private int endTime;
	
	public Active(int startTime, int endTime) {
		this.startTime = startTime;
		this.endTime = endTime;
	}
	
	public int getStartTime() {
		return startTime;
	}

	public void setStartTime(int startTime) {
		this.startTime = startTime;
	}

	public int getEndTime() {
		return endTime;
	}

	public void setEndTime(int endTime) {
		this.endTime = endTime;
	}

	@Override
	public int compareTo(Active o) {
		if (this.endTime > o.getEndTime()) {
			return 1;
		}else if (this.endTime == o.endTime) {
			return 0;
		}else {
			return 0;
		}
	}

	@Override
	public String toString() {
		return "Active [startTime=" + startTime + ", endTime=" + endTime + "]";
	}
}
